#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        if (root->val < 2) return root->val;

        int leftVal = evaluateTree(root->left);
        int rightVal = evaluateTree(root->right);

        if (root->val == 2) return leftVal | rightVal;
        else if (root->val == 3) return leftVal & rightVal;
        else return root->val;
    }
};


class Solution {
public:
    bool evaluateTree(TreeNode* root) {
        //if(root->val < 2) return root->val;

        if (root->val == 2) return evaluateTree(root->left) | evaluateTree(root->right);
        else if (root->val == 3) return evaluateTree(root->left) & evaluateTree(root->right);
        else return root->val;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    long long ans = 0;

    int sumNumbers(TreeNode* root) {
        _sumNumbers(root, 0);
        return ans;
    }

    void _sumNumbers(TreeNode* root, long long sum)
    {
        if (!root->left && !root->right) {
            ans += sum * 10 + root->val;
            cout << sum * 10 + root->val << endl;
            return;
        }
        if (root->left != nullptr) _sumNumbers(root->left, sum * 10 + root->val);
        if (root->right != nullptr) _sumNumbers(root->right, sum * 10 + root->val);
    }

};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if (root->left) root->left = pruneTree(root->left);
        if (root->right) root->right = pruneTree(root->right);
        if (root->left == nullptr && root->right == nullptr && root->val == 0) {
            delete root;
            return nullptr;
        }
        else return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> vt;

    bool isValidBST(TreeNode* root) {
        _isValidBST(root);
        int len = vt.size();
        for (int i = 1; i < len; i++) {
            if (vt[i] <= vt[i - 1])
                return false;
        }
        return true;
    }

    void _isValidBST(TreeNode* root)
    {
        if (root == nullptr) return;
        _isValidBST(root->left);
        vt.push_back(root->val);
        _isValidBST(root->right);
    }

};

class Solution {
public:
    long long prev = -1000000000000;

    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        int left = isValidBST(root->left);
        if (prev >= root->val) return false;
        else prev = root->val;
        int right = isValidBST(root->right);
        return left && right;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int count;

    int kthSmallest(TreeNode* root, int k) {
        count = k;
        _kthSmallest(root);
        return ans;
    }

    void _kthSmallest(TreeNode* root)
    {
        if (root == nullptr) return;
        _kthSmallest(root->left);
        count--;
        if (count == 0) {
            ans = root->val;
            return;
        }
        _kthSmallest(root->right);
    }

};


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> ans;
    vector<string> binaryTreePaths(TreeNode* root) {
        string tmp;
        _binaryTreePaths(root, tmp);
        return ans;
    }

    void _binaryTreePaths(TreeNode* root, string& tmpStr)
    {
        if (root->left == nullptr && root->right == nullptr) {
            ans.push_back(tmpStr + to_string(root->val));
            return;
        }
        int len = tmpStr.size();
        tmpStr += to_string(root->val) + "->";
        if (root->left) _binaryTreePaths(root->left, tmpStr);
        if (root->right) _binaryTreePaths(root->right, tmpStr);
        tmpStr.resize(len);
    }
};